<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>二分查找</title>
</head>
<body>
   <script>
    /** 二分查找
     *  
     * 工作原理：分治策略。数组必须是有序数组。无序数组不适用。每轮减少一半的搜索范围，直至找到目标为止
     * 
     * 流程：
     * 1.计算中心点索引，mid = (start + end) / 2
     * 2.arrs[mid] 和 target 比较
     *   arrs[mid] > target
     *   arrs[mid] < target
     *   arrs[mid] = target
     * 3.没有找到返回 -1
     * 
     * 时间复杂度：O(logn)   空间复杂度：O(1)
     */

    function binarySearch(arrs, target) {
      let start=0, end=arrs.length - 1; // 定义开始索引和结束索引
      while (start < end) {
        const mid = Math.floor((start + end) / 2) // 取数组中心位置的索引
        if(arrs[mid] > target) { // 目标值在数组左侧
          end = mid - 1
        } else if(arrs[mid] < target) { // 目标值在数组右侧
          start = mid + 1
        } else { // 目标值等于该值
          return mid
        }
      }
      return -1;
    }

    let data = new Array(100).fill(0).map((item, i) => 2*i)
    const result = binarySearch(data, 6)
    document.write(data, '二分查找 result：', result)
   </script>
</body>
</html>